package cn.initcap.algorithm.leetcode;

/**
 * 01背包问题
 * 有一个背包，它的容量为C（Capacity），现在有n种不同的物品，编号为0...n-1，其中每一件物品的重量为w(i)，价值为v(i)。
 * 问可以向这个背包种盛放那些物品，使得在不超过背包容量的基础上，物品的总价值最大。
 * <p>
 * 暴力解法：每一件物品都可以放进背包，也可以不放进背包。
 * O((2^n) * n)
 *
 * @author initcap
 * @date Created in 2020/1/23 17:11.
 */
public class Knapsack01 {

    private int[][] memo;

    /**
     * 递归方式实现，记忆化搜索
     *
     * @param w 权重数组
     * @param v 价值数组
     * @param c 当前容量
     * @return 最大总和
     */
    private int knapsack01(int[] w, int[] v, int c) {
        int n = w.length;
        memo = new int[n][c + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c + 1; j++) {
                memo[i][j] = -1;
            }
        }
        return bestValue(w, v, n - 1, c);
    }

    /**
     * @param w     重量
     * @param v     价值
     * @param index 下标
     * @param c     当前的容量
     * @return 最优解
     */
    private int bestValue(int[] w, int[] v, int index, int c) {
        if (index < 0 || c <= 0) {
            return 0;
        }
        if (memo[index][c] != -1) {
            return memo[index][c];
        }
        // 尝试向背包中放入新的物品
        int res = bestValue(w, v, index - 1, c);
        if (c >= w[index]) {
            res = Math.max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));
        }
        memo[index][c] = res;
        return res;
    }

    /**
     * 动态搜索方式解决
     *
     * @param w 权重数组
     * @param v 价值数组
     * @param c 指定的容量
     * @return 最优解的最大总和
     */
    private int knapsack01dynamic(int[] w, int[] v, int c) {
        if (w.length != v.length) {
            throw new IllegalArgumentException("权重素组长度需要和价值数组长度想等");
        }
        int n = w.length;
        if (n == 0) {
            return 0;
        }
        int[][] mem = new int[n][c + 1];
        // 给二维数组初始化数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c + 1; j++) {
                mem[i][j] = -1;
            }
        }
        // 初始化第0个的数组
        for (int i = 0; i <= c; i++) {
            // 如果能容纳将就将其放入，否则为0
            mem[0][i] = i >= w[0] ? v[0] : 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c; j++) {
                mem[i][j] = mem[i - 1][j];
                if (j >= w[i]) {
                    mem[i][j] = Math.max(mem[i][j], v[i] + mem[i - 1][j - w[i]]);
                }
            }
        }
        return mem[n - 1][c];
    }

    /**
     * 动态搜索方式解决，优化空间复杂度O(c)
     *
     * @param w 权重数组
     * @param v 价值数组
     * @param c 指定的容量
     * @return 最优解的最大总和
     */
    private int knapsack01dynamicupper(int[] w, int[] v, int c) {
        if (w.length != v.length) {
            throw new IllegalArgumentException("权重素组长度需要和价值数组长度想等");
        }
        int n = w.length;
        if (n == 0) {
            return 0;
        }
        // 将初始化的数据改为两行，轮流使用
        int[][] mem = new int[2][c + 1];
        // 给二维数组初始化数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c + 1; j++) {
                mem[i][j] = -1;
            }
        }
        // 初始化第0个的数组
        for (int i = 0; i <= c; i++) {
            // 如果能容纳将就将其放入，否则为0
            mem[0][i] = i >= w[0] ? v[0] : 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < c; j++) {
                mem[i % 2][j] = mem[(i - 1) % 2][j];
                if (j >= w[i]) {
                    mem[i % 2][j] = Math.max(mem[i % 2][j], v[i] + mem[(i - 1) % 2][j - w[i]]);
                }
            }
        }
        return mem[(n - 1) % 2][c];
    }

    /**
     * 动态搜索方式解决，优化空间复杂度O(c)
     *
     * @param w 权重数组
     * @param v 价值数组
     * @param c 指定的容量
     * @return 最优解的最大总和
     */
    private int knapsack01dynamicupper2(int[] w, int[] v, int c) {
        if (w.length != v.length) {
            throw new IllegalArgumentException("权重素组长度需要和价值数组长度想等");
        }
        int n = w.length;
        if (n == 0) {
            return 0;
        }
        // 将初始化的数据改为两行，轮流使用
        int[] mem = new int[c + 1];
        // 给二维数组初始化数据
        for (int i = 0; i < n; i++) {
            mem[i] = -1;
        }
        // 初始化第0个的数组
        for (int i = 0; i <= c; i++) {
            // 如果能容纳将就将其放入，否则为0
            mem[i] = i >= w[0] ? v[0] : 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = c; j >= w[i]; j--) {
                mem[j] = Math.max(mem[j], v[i] + mem[j - w[i]]);
            }
        }
        return mem[c];
    }

}
